# 团灭 LeetCode 打家劫舍问题
# 198. 打家劫舍
a = [1, 2, 3, 1]


def rob(nums: list):
    return dp(nums, 0)


# 递归解法
def dp(nums: list, start):
    if start >= len(nums):
        return 0
    res = max(
        # 不抢，去下家
        dp(nums, start + 1),
        # 抢，去下下家
        nums[start] + dp(nums, start + 2)
    )
    return res


print(rob(a))


# dp table解法
def dp2(nums: list):
    n = len(nums)
    # dp[i] = x表示：
    # 从第i间房子开始抢劫，最多能抢到的钱为x
    # base case: dp[n] = 0
    d = [0 for i in range(0, n + 2)]
    for i in range(n - 1, -1, -1):
        # print(i, end=' ')
        d[i] = max(d[i + 1], nums[i] + d[i + 2])
    return d[0]


print(dp2(a))


# dp table解法2
def dp3(nums: list):
    # 用dp[i]表示前i家获取的最高金额，第i阶段的决策就是两种：偷、不偷
    # 典型的动态规划问题，dp[i]=max(dp[i-1],dp[i-2]+nums[i])
    # 每个阶段确定一家偷还是不偷，所以决策就是偷和不偷两种
    n = len(nums)
    d = [0 for i in range(0, n + 1)]
    d[0] = 0
    d[1] = nums[0]
    for i in range(2, n + 1, 1):
        # print(i, end=' ')
        d[i] = max(d[i - 1], nums[i - 1] + d[i - 2])
    return d[n]


print(dp3(a))
